//逆序对
//https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
public class Test {
    public static void main(String[] args) {
        //
    }
}

class Solution {
    int count = 0;
    public int reversePairs(int[] record) {
        int l = 0;
        int r = record.length - 1;
        fun(record,l,r);
        //return count-1==0?1:count-1;
        return count;

    }
    private void fun(int[] record, int l, int r) {
        //[l,r]需要进行逆序对查找的区间
        if(r-l+1<2) return;//元素个数为1，不能再进行查找（找不到了）
        int mid = l + (r - l) / 2;//分割这个区间，分别进行查找
        fun(record,l,mid);
        fun(record,mid+1,r);
        //排序
        sort1(record,l,mid);
        sort1(record,mid+1,r);
        //左右分别出具一个进行查找
        comPare(record,l,r,mid);

    }

    //排序函数
    private void sort1(int[] record, int l, int r) {
        for (int i = l; i <= r; i++) {

            for (int j = l; j < r; j++) {
                if (record[j] > record[j + 1]) {
                    // 交换 arr[j] 和 arr[j+1]
                    int temp = record[j];
                    record[j] = record[j + 1];
                    record[j + 1] = temp;

                }
            }

        }
    }
    private void swap(int[] record, int l, int r){
        int temp = record[l];
        record[l] = record[r];
        record[r] = temp;
    }

    private void comPare(int[] record, int l, int r,int mid){
        int cur1 = l;
        int cur2 = mid+1;
        while(cur1 <= mid && cur2<=r){
            if(record[cur1] > record[cur2]){
                count+=(mid-cur1+1);
                cur2++;
            }else{
                cur1++;
            }
        }
    }
}